package src.dynamic_programming;

/**
 * @author starsea
 * @date 2024-09-11 20:36
 */

public class Test10 {
    public static void main(String[] args) {
        int[][] d={{1,3,1},{1,5,1},{4,2,1}};
        int ans=minPathSum(d);
        System.out.println(ans);
    }
    public static int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        //创建dp
        int[][] dp=new int[m+1][n+2];
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<n+2;j++)
            {
                dp[i][j]=0x3f3f3f;
            }
        }
        dp[0][1]=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<n+1;j++)
            {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}
